package com.guaoran.algorithm.node.list;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auth gucheng
 * @Desc 设计一个关于 LRU 的数据结构进行缓存存储
 * @From 字节跳动
 * https://leetcode.com/problems/lru-cache/
 * @Date 2020/12/21 下午4:11
 */
public class LRUCache {
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // cache is {1=1}
        lRUCache.put(2, 2); // cache is {1=1, 2=2}
        lRUCache.get(1);    // return 1
        lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
        lRUCache.get(2);    // returns -1 (not found)
        lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
        lRUCache.get(1);    // return -1 (not found)
        lRUCache.get(3);    // return 3
        lRUCache.get(4);    // return 4
        int param = lRUCache.get(1);
        System.out.println(param);
    }

    private class CacheNode{
        CacheNode prev;
        CacheNode next;
        int key;
        int val;

        public CacheNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 容量
    int capacity;
    // 为了实现时间复杂度为 O(1) ，采用 HashMap 数据结构
    Map<Integer,CacheNode> cacheNodeMap = new HashMap<>();
    // 为了方便移动元素，这里  采用双向链表
    CacheNode head = new CacheNode(-1,-1);
    CacheNode tail = new CacheNode(-1,-1);


    public LRUCache(int capacity){
        this.capacity = capacity;
        this.tail.prev = head;
        this.head.next = tail;
    }

    public int get(int key){
        if(!cacheNodeMap.containsKey(key)){
            return -1;
        }
        CacheNode current = cacheNodeMap.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        moveToTail(current);
        return current.val;
    }

    public void put(int key,int value){
        // 如果存在，则修改 val
        if(get(key) != -1){
            cacheNodeMap.get(key).val = value;
            return;
        }
        // 如果长度满了，则删除 第一个元素
        if(cacheNodeMap.size()==capacity){
            cacheNodeMap.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }

        // 添加元素
        CacheNode current = new CacheNode(key,value);
        cacheNodeMap.put(key,current);

        moveToTail(current);
    }

    // 移动节点到tail的前面
    public void moveToTail(CacheNode current){
        current.next = tail;
        current.prev = tail.prev;
        tail.prev.next = current;
        tail.prev = current;
    }
}
